﻿/**
 * Copyright 2019 Oskar Sigvardsson
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace GK {
	public class DelaunayCalculator {

		int highest = -1;
		IList<Vector2> verts;

		List<int> indices;
		List<TriangleNode> triangles;

		/// <summary>
		/// Creates a new Delaunay triangulation calculator
		/// </summary>
		public DelaunayCalculator() {
			triangles = new List<TriangleNode>();
			indices = new List<int>();
		}

		/// <summary>
		/// Calculate the triangulation of the supplied vertices
		/// </summary>
		/// <param name="verts">List of vertices to use for calculation</param>
		/// <returns>The calculated Delaunay triangulation<returns>
		public DelaunayTriangulation CalculateTriangulation(IList<Vector2> verts) {
			DelaunayTriangulation result = null;
			CalculateTriangulation(verts, ref result);

			return result;
		}

		/// <summary>
		/// Calculate the triangulation of the supplied vertices.
		///
		/// This overload allows you to reuse the result object, to prevent
		/// garbage from being created.
		/// </summary>
		/// <param name="verts">List of vertices to use for calculation</param>
		/// <param name="result">Result object to store the triangulation in</param>
		public void CalculateTriangulation(IList<Vector2> verts, ref DelaunayTriangulation result) {
			if (verts == null) {
				throw new ArgumentNullException("points");
			}
			if (verts.Count < 3) {
				throw new ArgumentException("You need at least 3 points for a triangulation");
			}

			triangles.Clear();
			this.verts = verts;

			highest = 0;

			for (int i = 0; i < verts.Count; i++) {
				if (Higher(highest, i)) {
					highest = i;
				}
			}

			//ShuffleIndices();

			// Add first triangle, the bounding triangle.
			triangles.Add(new TriangleNode(-2, -1, highest));

			RunBowyerWatson();
			GenerateResult(ref result);

			this.verts = null;
		}

		bool Higher(int pi0, int pi1) {
			if (pi0 == -2) {
				return false;
			} else if (pi0 == -1) {
				return true;
			} else if (pi1 == -2) {
				return true;
			} else if (pi1 == -1) {
				return false;
			} else {
				var p0 = verts[pi0];
				var p1 = verts[pi1];

				if (p0.y < p1.y) {
					return true;
				} else if (p0.y > p1.y) {
					return false;
				} else {
					return p0.x < p1.x;
				}
			}
		}

		/// <summary>
		/// Run the algorithm
		/// </summary>
		void RunBowyerWatson() {
			// For each point, find the containing triangle, split it into three
			// new triangles, call LegalizeEdge on all edges opposite the newly
			// inserted points
			for (int i = 0; i < verts.Count; i++) {
				//var pi = indices[i];
				var pi = i;

				if (pi == highest) continue;

				// Index of the containing triangle
				var ti = FindTriangleNode(pi);

				var t = triangles[ti];

				// The points of the containing triangle in CCW order
				var p0 = t.P0;
				var p1 = t.P1;
				var p2 = t.P2;

				// Indices of the newly created triangles.
				var nti0 = triangles.Count;
				var nti1 = nti0 + 1;
				var nti2 = nti0 + 2;

				// The new triangles! All in CCW order
				var nt0 = new TriangleNode(pi, p0, p1);
				var nt1 = new TriangleNode(pi, p1, p2);
				var nt2 = new TriangleNode(pi, p2, p0);


				// Setting the adjacency triangle references.  Only way to make
				// sure you do this right is by drawing the triangles up on a
				// piece of paper.
				nt0.A0 = t.A2;
				nt1.A0 = t.A0;
				nt2.A0 = t.A1;

				nt0.A1 = nti1;
				nt1.A1 = nti2;
				nt2.A1 = nti0;

				nt0.A2 = nti2;
				nt1.A2 = nti0;
				nt2.A2 = nti1;

				// The new triangles are the children of the old one.
				t.C0 = nti0;
				t.C1 = nti1;
				t.C2 = nti2;

				triangles[ti] = t;

				triangles.Add(nt0);
				triangles.Add(nt1);
				triangles.Add(nt2);

				if (nt0.A0 != -1) LegalizeEdge(nti0, nt0.A0, pi, p0, p1);
				if (nt1.A0 != -1) LegalizeEdge(nti1, nt1.A0, pi, p1, p2);
				if (nt2.A0 != -1) LegalizeEdge(nti2, nt2.A0, pi, p2, p0);
			}
		}

		/// <summary>
		/// Filter the points array and triangle tree into a readable result.
		/// </summary>
		void GenerateResult(ref DelaunayTriangulation result) {
			if (result == null) {
				result = new DelaunayTriangulation();
			}

			result.Clear();

			for (int i = 0; i < verts.Count; i++) {
				result.Vertices.Add(verts[i]);
			}

			for (int i = 1; i < triangles.Count; i++) {
				var t = triangles[i];

				if (t.IsLeaf && t.IsInner) {
					result.Triangles.Add(t.P0);
					result.Triangles.Add(t.P1);
					result.Triangles.Add(t.P2);
				}
			}

		}

		/// <summary>
		/// Shuffle the indices array. Optimal runtime depends on shuffled
		/// input.
		/// </summary>
		void ShuffleIndices() {
			indices.Clear();
			indices.Capacity = verts.Count;

			for (int i = 0; i < verts.Count; i++) {
				indices.Add(i);
			}

			Debug.Assert(indices.Count == verts.Count);

			for (int i = 0; i < verts.Count - 1; i++) {
				var j = UnityEngine.Random.Range(i, verts.Count);

				var tmp = indices[i];
				indices[i] = indices[j];
				indices[j] = tmp;
			}
		}

		/// <summary>
		/// Find the leaf of the triangles[ti] subtree that contains a given
		/// edge.
		///
		/// We need this because when we split or flip triangles, the adjacency
		/// references don't update, so even if the adjacency triangles were
		/// leaves when the node was created, they might not be leaves later.
		/// If they aren't, they're going to be the ancestor of the correct
		/// leaf, so this method goes down the tree finding the right leaf.
		/// </summary>
		int LeafWithEdge(int ti, int e0, int e1) {
			Debug.Assert(triangles[ti].HasEdge(e0, e1));

			while (!triangles[ti].IsLeaf) {
				var t = triangles[ti];

				if (t.C0 != -1 && triangles[t.C0].HasEdge(e0, e1)) {
					ti = t.C0;
				} else if (t.C1 != -1 && triangles[t.C1].HasEdge(e0, e1)) {
					ti = t.C1;
				} else if (t.C2 != -1 && triangles[t.C2].HasEdge(e0, e1)) {
					ti = t.C2;
				} else {
					Debug.Assert(false);
					throw new System.Exception("This should never happen");
				}
			}

			return ti;
		}

		/// <summary>
		/// Is the edge legal, or does it need to be flipped?
		/// </summary>
		bool LegalEdge(int k, int l, int i, int j) {
			Debug.Assert(k != highest && k >= 0);

			var lMagic = l < 0;
			var iMagic = i < 0;
			var jMagic = j < 0;

			Debug.Assert(!(iMagic && jMagic));

			if (lMagic) {
				return true;
			} else if (iMagic) {
				Debug.Assert(!jMagic);

				var p = verts[l];
				var l0 = verts[k];
				var l1 = verts[j];

				return Geom.ToTheLeft(p, l0, l1);
			} else if (jMagic) {
				Debug.Assert(!iMagic);

				var p = verts[l];
				var l0 = verts[k];
				var l1 = verts[i];

				return !Geom.ToTheLeft(p, l0, l1);
			} else {
				Debug.Assert(k >= 0 && l >= 0 && i >= 0 && j >= 0);

				var p = verts[l];
				var c0 = verts[k];
				var c1 = verts[i];
				var c2 = verts[j];

				Debug.Assert(Geom.ToTheLeft(c2, c0, c1));
				Debug.Assert(Geom.ToTheLeft(c2, c1, p));

				return !Geom.InsideCircumcircle(p, c0, c1, c2);
			}
		}

		/// <summary>
		/// Key part of the algorithm. Flips edges if they need to be flipped,
		/// and recurses.
		///
		/// pi is the newly inserted point, creating a new triangle ti0.
		/// The adjacent triangle opposite pi in ti0 is ti1. The edge separating
		/// the two triangles is li0 and li1.
		///
		/// Checks if the (li0, li1) edge needs to be flipped. If it does,
		/// creates two new triangles, and recurses to check if the newly
		/// created triangles need flipping.
		/// <summary>
		void LegalizeEdge(int ti0, int ti1, int pi, int li0, int li1) {
			// ti1 might not be a leaf node (ti0 is guaranteed to be, it was
			// just created), so find the current correct leaf.
			ti1 = LeafWithEdge(ti1, li0, li1);

			var t0 = triangles[ti0];
			var t1 = triangles[ti1];
			var qi = t1.OtherPoint(li0, li1);

			Debug.Assert(t0.HasEdge(li0, li1));
			Debug.Assert(t1.HasEdge(li0, li1));
			Debug.Assert(t0.IsLeaf);
			Debug.Assert(t1.IsLeaf);
			Debug.Assert(t0.P0 == pi || t0.P1 == pi || t0.P2 == pi);
			Debug.Assert(t1.P0 == qi || t1.P1 == qi || t1.P2 == qi);


			//var p = points[pi];
			//var q = points[qi];
			//var l0 = points[li0];
			//var l1 = points[li1];

			if (!LegalEdge(pi, qi, li0, li1)) {
				var ti2 = triangles.Count;
				var ti3 = ti2 + 1;

				var t2 = new TriangleNode(pi, li0, qi);
				var t3 = new TriangleNode(pi, qi, li1);

				t2.A0 = t1.Opposite(li1);
				t2.A1 = ti3;
				t2.A2 = t0.Opposite(li1);

				t3.A0 = t1.Opposite(li0);
				t3.A1 = t0.Opposite(li0);
				t3.A2 = ti2;

				triangles.Add(t2);
				triangles.Add(t3);

				var nt0 = triangles[ti0];
				var nt1 = triangles[ti1];

				nt0.C0 = ti2;
				nt0.C1 = ti3;

				nt1.C0 = ti2;
				nt1.C1 = ti3;

				triangles[ti0] = nt0;
				triangles[ti1] = nt1;

				if (t2.A0 != -1) LegalizeEdge(ti2, t2.A0, pi, li0, qi);
				if (t3.A0 != -1) LegalizeEdge(ti3, t3.A0, pi, qi, li1);
			}
		}

		/// <summary>
		/// Find the leaf triangle in the triangle tree containing a certain point.
		/// </summary>
		int FindTriangleNode(int pi) {
			var curr = 0;

			while (!triangles[curr].IsLeaf) {
				var t = triangles[curr];

				if (t.C0 >= 0 && PointInTriangle(pi, t.C0)) {
					curr = t.C0;
				} else if (t.C1 >= 0 && PointInTriangle(pi, t.C1)) {
					curr = t.C1;
				} else {
					curr = t.C2;
				}
			}

			return curr;
		}

		/// <summary>
		/// Convenience method to check if a point is inside a certain triangle.
		/// </summary>
		bool PointInTriangle(int pi, int ti) {
			var t = triangles[ti];
			return ToTheLeft(pi, t.P0, t.P1)
				&& ToTheLeft(pi, t.P1, t.P2)
				&& ToTheLeft(pi, t.P2, t.P0);
		}

		/// <summary>
		/// Is the point to the left of the edge?
		/// </summary>
		bool ToTheLeft(int pi, int li0, int li1) {
			if (li0 == -2) {
				return Higher(li1, pi);
			} else if (li0 == -1) {
				return Higher(pi, li1);
			} else if (li1 == -2) {
				return Higher(pi, li0);
			} else if (li1 == -1) {
				return Higher(li0, pi);
			} else {
				Debug.Assert(li0 >= 0);
				Debug.Assert(li1 >= 0);

				return Geom.ToTheLeft(verts[pi], verts[li0], verts[li1]);
			}
		}

		/// <summary>
		/// A single node in the triangle tree.
		///
		/// All parameters are indexes.
		/// </summary>
		struct TriangleNode {
			// The points of the triangle
			public int P0;
			public int P1;
			public int P2;

			// The child triangles of this triangle in the tree
			//
			// A value of -1 means "no child"
			public int C0;
			public int C1;
			public int C2;

			// The triangles adjacent to this triangle
			//
			// A0 is the adjacent triangle opposite to the P0 point (i.e. the A0
			// triangle has (P1, P2) as an edge.
			//
			// A value of -1 means "no adjacent triangle" (only true for
			// triangles with one edge on the bounding triangle).
			public int A0;
			public int A1;
			public int A2;

			// Is this a leaf triangle?
			public bool IsLeaf {
				get {
					return C0 < 0 && C1 < 0 && C2 < 0;
				}
			}

			/// <summary>
			/// Is this an "inner" triangle, part of the final triangulation, or
			/// is some part of this triangle connected to the bounding triangle.
			/// </summary>
			public bool IsInner {
				get {
					return P0 >= 0 && P1 >= 0 && P2 >= 0;
				}
			}

			public TriangleNode(int P0, int P1, int P2) {
				this.P0 = P0;
				this.P1 = P1;
				this.P2 = P2;

				this.C0 = -1;
				this.C1 = -1;
				this.C2 = -1;

				this.A0 = -1;
				this.A1 = -1;
				this.A2 = -1;
			}


			/// <summary>
			/// Does this triangle contain this edge?
			/// </summary>
			public bool HasEdge(int e0, int e1) {
				if (e0 == P0) {
					return e1 == P1 || e1 == P2;
				} else if (e0 == P1) {
					return e1 == P0 || e1 == P2;
				} else if (e0 == P2) {
					return e1 == P0 || e1 == P1;
				}

				return false;
			}


			/// <summary>
			/// Assuming p0 and p1 are one of P0 and P1, return the third point.
			/// </summary>
			public int OtherPoint(int p0, int p1) {
				if (p0 == P0) {
					if (p1 == P1) return P2;
					if (p1 == P2) return P1;
					throw new ArgumentException("p0 and p1 not on triangle");
				}
				if (p0 == P1) {
					if (p1 == P0) return P2;
					if (p1 == P2) return P0;
					throw new ArgumentException("p0 and p1 not on triangle");
				}
				if (p0 == P2) {
					if (p1 == P0) return P1;
					if (p1 == P1) return P0;
					throw new ArgumentException("p0 and p1 not on triangle");
				}

				throw new ArgumentException("p0 and p1 not on triangle");
			}


			/// <summary>
			/// Get the triangle opposite a certain point.
			/// </summary>
			public int Opposite(int p) {
				if (p == P0) return A0;
				if (p == P1) return A1;
				if (p == P2) return A2;
				throw new ArgumentException("p not in triangle");
			}

			/// <summary>
			/// For debugging purposes.
			/// </summary>
			public override string ToString() {
				if (IsLeaf) {
					return string.Format("TriangleNode({0}, {1}, {2})", P0, P1, P2);
				} else {
					return string.Format("TriangleNode({0}, {1}, {2}, {3}, {4}, {5})", P0, P1, P2, C0, C1, C2);
				}
			}
		}
	}
}
